/**
 * @author kaho
 * @since 2021/4/2
 */
public class _面试题_17_21_直方图的水量 {


    /**
     * 给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
     * @param height
     * @return
     */
    public static int trap(int[] height) {
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            sum+=height[i];
        }

        int volume = 0;
        int left = 0;
        int right = height.length-1;
        int high = 1;
        while (left < right) {
            while (left <= right && height[left]<high) {
                left++;
            }

            while (left <= right&&height[right]<high) {
                right--;
            }
            volume += right-left+1;
            high++;
        }
        return volume-sum;
    }

    public static void main(String[] args) {

        int trap = trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
    }
}
